//
// Description: 154. 滑动窗口
// Created by Loading on 2021/12/12.
//

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 1e6 + 10;

// 单调队列，存储下标
int a[N], q[N];

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // 队头和队尾
    int hh = 0, tt = -1;
    // 求窗口最小值
    for (int i = 0; i < n; ++i) {
        // 判断队头元素是否已经滑出窗口
        if (hh <= tt && q[hh] < i - k + 1) {
            ++hh;
        }
        while (hh <= tt && a[q[tt]] >= a[i]) {
            --tt;
        }
        q[++tt] = i;
        if (i - k + 1 >= 0) {
            cout << a[q[hh]] << ' ';
        }
    }
    cout << endl;

    hh = 0, tt = -1;
    // 求窗口最大值
    for (int i = 0; i < n; ++i) {
        // 判断队头元素是否已经滑出窗口
        if (hh <= tt && q[hh] < i - k + 1) {
            ++hh;
        }
        while (hh <= tt && a[q[tt]] <= a[i]) {
            --tt;
        }
        q[++tt] = i;
        if (i - k + 1 >= 0) {
            cout << a[q[hh]] << ' ';
        }
    }
    cout << endl;

    return 0;
}